Possible bipartition [DFS]¶
Time: O(|V| + |E|); Space: O(|V| + |E|); medium
Given a set of N people (numbered 1, 2, …, N), we would like to split everyone into two groups of any size.
Each person may dislike some other people, and they should not go into the same group.
Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.
Return true if and only if it is possible to split everyone into two groups in this way.
Example 1:
Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: True
Explanation:
group1 [1,4], group2 [2,3]
Example 2:
Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: False
Example 3:
Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: False
Notes:
1 <= N <= 2000
0 <= len(dislikes) <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].
1. Depth-First Search¶
Intuition It’s natural to try to assign everyone to a group. Let’s say people in the first group are red, and people in the second group are blue.
If the first person is red, anyone disliked by this person must be blue. Then, anyone disliked by a blue person is red, then anyone disliked by a red person is blue, and so on.
If at any point there is a conflict, the task is impossible, as every step logically follows from the first step. If there isn’t a conflict, then the coloring was valid, so the answer would be true.
Algorithm Consider the graph on N people formed by the given “dislike” edges. We want to check that each connected component of this graph is bipartite. For each connected component, we can check whether it is bipartite by just trying to coloring it with two colors. How to do this is as follows: * color any node red, * then all of it’s neighbors blue, * then all of those neighbors red, and so on. If we ever color a red node blue (or a blue node red), then we’ve reached a conflict.
[3]:
import collections
class Solution1(object):
"""
Time: O(N+E), where E is the length of dislikes.
Space: O(N+E).
"""
def possibleBipartition(self, N, dislikes):
"""
:type N: int
:type dislikes: List[List[int]]
:rtype: bool
"""
graph = collections.defaultdict(list)
for u, v in dislikes:
graph[u].append(v)
graph[v].append(u)
color = {}
def dfs(node, c = 0):
if node in color:
return color[node] == c
color[node] = c
return all(dfs(nei, c ^ 1) for nei in graph[node])
return all(dfs(node)
for node in range(1, N+1)
if node not in color)
[4]:
s = Solution1()
N = 4
dislikes = [[1,2],[1,3],[2,4]]
assert s.possibleBipartition(N, dislikes) == True
N = 3
dislikes = [[1,2],[1,3],[2,3]]
assert s.possibleBipartition(N, dislikes) == False
N = 5
dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
assert s.possibleBipartition(N, dislikes) == False
[7]:
import collections
class Solution2(object):
"""
Time: O(|V| + |E|)
Space: O(|V| + |E|)
"""
def possibleBipartition(self, N, dislikes):
"""
:type N: int
:type dislikes: List[List[int]]
:rtype: bool
"""
graph = [[] for _ in range(N)]
for u, v in dislikes:
graph[u-1].append(v-1)
graph[v-1].append(u-1)
color = [0]*N
color[0] = 1
q = collections.deque([0])
while q:
cur = q.popleft()
for nei in graph[cur]:
if color[nei] == color[cur]:
return False
elif color[nei] == -color[cur]:
continue
color[nei] = -color[cur]
q.append(nei)
return True
[8]:
s = Solution2()
N = 4
dislikes = [[1,2],[1,3],[2,4]]
assert s.possibleBipartition(N, dislikes) == True
N = 3
dislikes = [[1,2],[1,3],[2,3]]
assert s.possibleBipartition(N, dislikes) == False
N = 5
dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
assert s.possibleBipartition(N, dislikes) == False